/*
 * GSS3.cxx
 *
 *  Created on: 1:34:10 PM Nov 1, 2012
 *      Author: Pallab
 * "I have not failed, I have just found 10000 ways that won't work.
 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <numeric>
#include <stack>
#include <functional>
#include <bitset>
#include <iomanip>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;

#define foR(i1,st,ed) for(int i1 = st , j1 = ed ; i1 < j1 ; ++i1 )
#define fo(i1,ed) foR( i1 , 0 , ed )
#define foE(i1,st,ed) foR( i1, st, ed+1 )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )
#define line puts("")

inline void wait(double seconds) {
	double endtime = clock() + (seconds * CLOCKS_PER_SEC);
	while (clock() < endtime) {
		;
	}
}
#define T int
inline T fastIn() {
	register char c = 0;
	register T a = 0;
	bool neg = false;
	while (c < 33)
		c = getchar();
	while (c > 33) {
		if (c == '-') {
			neg = true;
		} else {
			a = (a * 10) + (c - '0');
		}
		c = getchar();
	}
	return neg ? -a : a;
}
inline void myOut(T a) {
	if (a) {
		int v = a % 10;
		myOut(a / 10);
		putchar((char) (v + '0'));
	}

}
inline void fastOut(T a) {
	if (a == T(0)) {
		putchar('0');
	} else if (a < T(0)) {
		putchar('-');
		myOut(-a);
	} else {
		myOut(a);
	}
}
const int MX = 50000;
int number_count;
int numbers[MX];
inline int maxx(int p, int q) {
	return p > q ? p : q;
}
inline int maxx(int p, int q, int r) {
	return maxx(p, maxx(q, r));
}
const int inf = -1023456789;
struct interval {
	int total_sum, pre, suf, bst_sum;
	interval() {
		total_sum = pre = suf = bst_sum = inf;
	}
	interval(int val) {
		total_sum = pre = suf = bst_sum = val;
	}
	interval(interval l, interval r) {
		total_sum = l.total_sum + r.total_sum;
		pre = maxx(l.pre, l.total_sum + r.pre);
		suf = maxx(r.suf, r.total_sum + l.suf);
		bst_sum = maxx(l.bst_sum, r.bst_sum, l.suf + r.pre);
	}
};
interval t[MX * 4];
#define L(v) ( v << 1 )
#define R(v) ( 1 + ( v << 1 ) )
#define M(x,y) ( (x+y)>>1 )

inline interval combine(interval l, interval r) {
	return interval(l, r);
}
void build(int v, int tl, int tr) {
	if (tl == tr) {
		t[v] = interval(numbers[tl]);
	} else {
		int tm = M(tl,tr);
		build(L(v), tl, tm);
		build(R(v), tm + 1, tr);
		t[v] = combine(t[L(v)], t[R(v)]);
	}
}
void update(int v, int tl, int tr, int pos, int newval) {
	if (tl == tr) {
		t[v] = interval(newval);
	} else {
		int tm = M(tl,tr);
		if (pos <= tm)
			update(L(v), tl, tm, pos, newval);
		else
			update(R(v), tm + 1, tr, pos, newval);
		t[v] = combine(t[L(v)], t[R(v)]);
	}
}
interval query(int v, int tl, int tr, int l, int r) {
	if (l == tl && tr == r)
		return t[v];
	int tm = M(tl,tr);
	if (r <= tm)
		return query(L(v), tl, tm, l, r);
	if (l > tm)
		return query(R(v), tm + 1, tr, l, r);
	return combine(query(L(v), tl, tm, l, tm),
			query(R(v), tm + 1, tr, tm + 1, r));
}
inline void read() {
	number_count = fastIn();
	fo(i,number_count)
		numbers[i] = fastIn();
}
inline void proc() {
	build(1, 0, number_count - 1);
	int query_count = fastIn(), type, l, r;
	fo(i,query_count)
	{
		type = fastIn(), l = fastIn(), r = fastIn();
		if (type) {
			//query l-r
			interval res = query(1, 0, number_count - 1, l - 1, r - 1);
			fastOut(res.bst_sum);
			line;
		} else {
			//put r in pos l
			update(1, 0, number_count - 1, l - 1, r);
		}
	}
}
int main() {
	int kase = 1;
#if defined( xerxes_pc )
	if (!freopen("in1", "r", stdin))
		puts("error opening file in "), assert(0);
	kase = 1;
#endif
	fo(i,kase)
	{
		read();
		proc();
	}
	return 0;
}
